1. Field of the Invention
The present invention relates to a network control system in a hyper cube type network used in a multi-processor interconnection system.
2. Description of the Related Art
As is well known, the hyper cube type network has a plurality of nodes (2.sup.n nodes, n&gt;0, integer), each node being arranged on an apex of the cube, a plurality of links connecting the nodes, and a plurality of processors, each connected to each node.
In general, two types of the multi-processor interconnection system are used, i.e., a multi-stage network and a multi-processor network.
The multi-stage network includes various types of networks based on differences in the connection configuration thereof. For example, an omega network, a delta network, a banyan network, a shuffle-exchange network, etc. In general, these types, for example, the omega network and the shuffle-exchange network, have a plurality of switch boxes, and each switch box generally has two input terminals and two output terminals. Each switch box can take two connection configurations, i.e., cross and straight corresponding to a bit "1" and a bit "0". The switch boxes are connected by links from input stages to output stages in accordance with the above connection configurations, to form communication paths.
In these types of multi-stage networks, however, although a high transfer speed can be achieved, a problem arises in that the number of communication paths which can be simultaneously used is limited, because the switch box can deal with only one communication path at a time.
The multi-processor network is constituted by a plurality of nodes and links connected between the nodes, wherein each node has at least one buffer memory for temporarily storing input messages. This type of network has connection configurations, such as, a ring type, tree type, hyper cube type, etc., in accordance with different arrangements of the nodes. In these types of network, however, a problem arises in that much time is required for writing/reading a message to and from the buffer memory. Thus, transmission of a message is delayed in an all-to-all burst communication when many loads are connected to the network.
The hyper cube type network can be obtained in both the multi-stage and the multi-processor type of network, depending upon the connection configuration of the nodes and the links, by rewriting a topology thereof. That is, a network having the hyper cube topology can exist in both multi-stage and multi-processor networks. In particular, it is possible to modify the shuffle-exchange network to the hyper cube topology by rewriting the structure thereof when the former does not have the hyper cube topology.
The present invention features an improvement of the total processing performance of the processors connected to the hyper cube type network, particularly, in an all-to-all burst communication. The all-to-all burst communication is a communication pattern in which each processor can simultaneously communicate to all processors including itself in the system. Therefore, in the present invention, all communication paths are structured to achieve an effective all-to-all burst communication in the hyper cube type network.
One example of the multi-stage network is disclosed in, New Generation Computing, 1984, "A Multi Page-Memory Architecture and A Multiport Disk-Cache System", by Yuzuru Tanaka. This network is constituted by a plurality of ports, a plurality of memory banks, a plurality of switch boxes, and a controller. The controller controls the connection of switch boxes based on a predetermined control program. In this reference, however, the network is formed between the ports and the memory banks. Further, the topology of the network is a type of the shuffle-exchange network, and the switch box comprises two inputs and two outputs. These are important differences from the present invention. Note, if the network of the reference is rewritten to the hyper cube topology, one half of the links are not used, and thus the processing performance is unsatisfactory.